package demo_0712;

public class T6_0327 {
    //给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildChild(preorder,inorder,0,inorder.length - 1);
    }
    public int priIndex;
    //先序遍历：根左右
    //中序遍历：左根右
    //先序遍历的第一个元素一定是根节点，所以先找到根节点，再在中序遍历中找到根节点的位置，根节点的左边就是左子树，右边就是右子树，然后递归构建左子树和右子树。
    // 1. 找到根节点
    // 2. 找到根节点在中序遍历中的位置
    // 3. 递归构建左子树和右子树
    // 4. 返回根节点
    private TreeNode buildChild(int[] preorder, int[] inorder, int inbegin, int inend) {
        //如果inbegin > inend，说明没有节点了，返回null
        if (inbegin > inend) return null;
        TreeNode root = new TreeNode(preorder[priIndex]);
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[priIndex]);
        //如果rootIndex == -1，说明没有根节点，返回null
        if (rootIndex == -1) return null;
        priIndex++;
        //先构建左子树，因为先序遍历的顺序是根左右，所以先构建左子树，再构建右子树
        root.left = buildChild(preorder,inorder,inbegin,rootIndex - 1);
        root.right = buildChild(preorder,inorder,rootIndex + 1,inend);
        return root;
    }

    private int findIndex(int[] inorder, int inbegin, int inend, int key) {
        for (int i = inbegin; i <= inend; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

}
